package Leetcode.StackAndQueue.maxSlidingWindow239;

import java.util.LinkedList;

public class Solution2 {
    public int[] maxSlidingWindow(int[] nums, int k) {
        int len = nums.length;
        if (len == 0 || nums == null || k == 0 || k == 1) {
            return nums;
        }
        int[] result = new int[len - k + 1];
        LinkedList<Integer> queue = new LinkedList<>();
        //声明一个双向队列
        for (int i = 0; i < len; i++) {
            //如果队列为空或者队列的尾下标对应的值大于当前的遍历的值  则删除队尾的值
            while (!queue.isEmpty() && nums[queue.peekLast()] <= nums[i]) {
                queue.pollLast();
            }
            //将下标加入队列
            queue.addLast(i);
            //判断队首的下标是否过期  过期的含义为 不是窗口中的值
            if (queue.peekFirst() <= i - k) {
                queue.poll();
            }
            //加入结果数组的判断依据 即从形成第一个窗口开始存放结果
            if (i + 1 >= k) {
                result[i + 1 - k] = nums[queue.peek()];
            }
        }


        return result;
    }

    public static void main(String[] args) {
        int[] nums = {1, 3, -1, -3, 5, 3, 6, 7};
        Solution2 solution = new Solution2();
        int[] res = solution.maxSlidingWindow(nums, 3);
        for (int i : res) {
            System.out.print(i);
        }

    }
}
